package job.jingdong;

import java.util.Scanner;

/**
 * @program: LeetCodePractice
 * @description:
 * @author: WongKee
 * @create: 2020-08-27 19:56
 * 某滚球游戏规则如下：球从入口处（第一层）开始向下滚动，每次可向下滚动一层，直到滚至最下面一层为止。球每次可滚至左下、下方或右下三个方格中的任意一个，每个方格都有一个得分，如下图所示。第1层有1个方格，第2层有3个方格，……，以此类推，第  n层有2*n-1个方格。设计一个算法，使得球从入口滚至最下面一层的总得分和最大
 * https://zihao.blog.csdn.net/article/details/108267758
 **/
public class ZongDeFenZuiDa {
    /*
n=3
     0   1   2   3   4
0            1
1        2   1   2
2    3   4   2   1   3


    * */
    private static int max_len=Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();

        int N=2*n-1;
        int[][] arr=new int[n][N];
        for(int i=1;i<=n;i++){
            for (int j=1;j<=i*2-1;j++){
                arr[i-1][n-i+j-1]=scanner.nextInt();
            }

        }

        for (int i=0;i<n;i++){
            for (int j=0;j<N;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
        //入口位置（0，n-1）
        dfs(arr,n,N,0,n-1,n-1,0,0);
        System.out.println(max_len);


    }
    public static void dfs(int[][] arr,int m,int n,int x,int y,int depth,int level,int value){
        if(x<0||x>=m||y<0||y>=n||level>depth){
            return;
        }
        value+=arr[x][y];
        if(level==depth){
            max_len=max_len>value?max_len:value;
        }
        //dfs(arr,m,n,);
        /*
         arr[x+1][y]
        arr[x+1][y-1]
        arr[x+1][y+1]
        * */
        dfs(arr,m,n,x+1,y,depth,level+1,value);
        dfs(arr,m,n,x+1,y-1,depth,level+1,value);
        dfs(arr,m,n,x+1,y+1,depth,level+1,value);
    }
}
